
"""
给你一个字符串 s，找到 s 中最长的 回文 子串。
"""

class Solution:
    """
    暴力法，submit超时
    """
    # def longestPalindrome(self, s: str) -> str:
    #     huiwenchuan = ""#保存最长回文字串
    #     for i in range(0,len(s)):
    #         sub_s = "" #字串初始化
    #         for j in range(i,len(s)):
    #             sub_s += s[j] #切割出字串
    #
    #             sub_len = len(sub_s)
    #
    #             flag = True #标记字串是否是回文 是回文赋值为True 不是赋值为False
    #             for m in range(0,sub_len):
    #                 if sub_s[m] != sub_s[sub_len-1-m]: #不是回文
    #                     flag = False
    #                     break
    #             if flag :
    #                 if len(sub_s) > len(huiwenchuan):
    #                     huiwenchuan = sub_s
    #     return huiwenchuan

    """
    中心扩展法
    """
    def longestPalindrome(self, s: str) -> str:
        def expand(left,right):
            while left >=0 and right<len(s) and s[left] == s[right]:
                left-=1
                right+=1
            return s[left+1:right]

        huiwenchuan = ""
        for i in range(len(s)):

            even = expand(i,i+1)#偶数长度

            odd = expand(i,i)#奇数长度
            huiwenchuan = max(huiwenchuan,odd,even,key=len)
        return huiwenchuan
p = Solution()
print(p.longestPalindrome("12345432167"))